package problem347;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

//347.前k个高频元素
//https://leetcode.cn/problems/top-k-frequent-elements/?envType=study-plan-v2&envId=top-100-liked

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int x : nums) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }

        //建小根堆
        PriorityQueue<Map.Entry<Integer, Integer>> queue =
                new PriorityQueue<>((a, b)->a.getValue()-b.getValue());

        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue.add(entry);
            if(queue.size() > k) queue.poll();
        }
        int[] ret = new int[k];
        for(int i = 0; i<k; i++) {
            ret[i] = queue.poll().getKey();
        }
        return ret;
    }
}